package lianxi;

/**
 * 自定义链表类
 * 
 * 模拟一个单向链表(最后做) 链表有增删改查等功能 节点也有增删改查等功能 打印链表 先添加的节点在第一位
 * 
 * @author lenovo
 * @Date 2020年7月19日
 * @Time 下午5:09:58
 * @param <T>
 */
public class NodeDemo<T> {
	// 链表是由结点构成的,要实现链表和结点的增删改查,首先要自定义及结点的成员内部类
	private class Node {
		private T data;
		private Node next;

		public Node() {
		}

		public Node(T data, Node next) {
			this.data = data;
			this.next = next;
		}
	}

	private Node head;// 链表的头结点
	private Node tail;// 链表的尾结点
	int size;

	public NodeDemo(T data) {
		head = new Node(data, null);
		tail = head;
		size++;
	}

	public NodeDemo() {
		head = null;
		tail = null;
	}

	/**
	 * 插入数据,先添加的结点在第一位,所以每次都在后边添加元素
	 * 
	 * @param t
	 */
	public void add(T t) {
		// 如果头结点为空,那么说明是第一个元素,直接new一个结点即可 
		if (head == null) {
			head = new Node(t, null);
			tail = head;
		} else {
			Node node = new Node(t, null);// 创建一个新的结点
			tail.next = node;// 尾结点的 next 赋值为新创建的结点
			tail = node;// 将链表的尾结点指向新的结点,以便继续插入新的元素
		}
		size++;
	}

	/**
	 * 删除结点,返回结点的数据
	 * 
	 * @param index
	 * @return
	 */
	public T delete(int index) {
		Node dNode = null;
		if (index < 0 || index > size - 1) {
			throw new IndexOutOfBoundsException("链表越界");
		}
		if (index == 0) {
			dNode = head;
			head = head.next;
		} else {
			Node p = findNodeByIndex(index - 1);
			dNode = p.next;
			p.next = dNode.next;
			dNode.next = null;
		}
		return dNode.data;

	}

	/**
	 * 查询结点(根据位置)
	 * 
	 * @param index
	 * @return
	 */
	public Node findNodeByIndex(int index) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("链表越界");
		}
		Node current = head;
		int t = 0;
		while (current != null) {
			if (t == index) {
				break;
			}
			current = current.next;
			t++;
		}
		return current;
	}

	/**
	 * 打印
	 */
	@Override
	public String toString() {
		Node node = head;
		StringBuffer sb = new StringBuffer();
		while (node != null) {
			sb.append(node.data + " ");
			node = node.next;
		}
		return sb.toString();
	}

	public static void main(String[] args) {
		NodeDemo<String> nd = new NodeDemo<String>();
		nd.add("asd");
		nd.add("qwer");
		nd.add("czxv");
		nd.add("gf");
		System.out.println(nd);
		System.out.println("删除第 2 个位置的结点 " + nd.delete(2));
		
		System.out.println("查询第 2 个位置的结点 " + nd.findNodeByIndex(2).data);
	}

}
